package main

import (
	"fmt"
	"time"
)

//DP思想

func maxProfit(prices []int) int {
	size := len(prices)
	min := 0
	max := 0
	if size <= 1 {
		return 0
	}

	min = prices[0]
	for i := 1; i < size; i++ {
		if max < prices[i]-min {
			max = prices[i] - min
		}
		if min > prices[i] {
			min = prices[i]
		}

		fmt.Println(max, min)
	}

	return max
}

// func maxProfit(prices []int) int {
// 	max := 0
// 	temp := 0
// 	size := len(prices)
// 	for i := 0; i < size; i++ {
// 		for j := i + 1; j < size; j++ {
// 			temp = prices[j] - prices[i]
// 			if max < temp {
// 				max = temp
// 			}
// 		}
// 	}

// 	return max
// }

func main() {
	start := time.Now()
	nums1 := []int{3, 3, 4, 5, 2, 3, 4, 6, 5, 4, 3, 2, 31, 2, 3, 4, 1}
	des := maxProfit(nums1)
	cost := time.Since(start)
	fmt.Println(des)
	fmt.Println(cost)

}
